//542 01矩阵
/*
给定一个由 0 和 1 组成的二维矩阵，求每个位置到最近的 0 的距离

输入输出样例
	输入是一个二维 0-1 数组，输出是一个同样大小的非负整数数组，表示每个位置到最近的 0
的距离

Input:
[[0,0,0],
[0,1,0],
[1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]

*/
vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
{
	if (matrix.empty())
		return {};
	int n = matrix.size(), m = matrix[0].size();
	vector<vector<int>> dp(n, vector<int>(m, INT_MAX - 1));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (matrix[i][j] == 0)
			{
				dp[i][j] = 0;
			}
			else
			{
				if (j > 0)
				{
					dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
				}
				if (i > 0)
				{
					dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
				}
			}
		}
	}
	for (int i = n - 1; i >= 0; --i)
	{
		for (int j = m - 1; j >= 0; --j)
		{
			if (matrix[i][j] != 0)
			{
				if (j < m - 1)
				{
					dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
				}
				if (i < n - 1)
				{
					dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
				}
			}
		}
	}
	return dp;
}
